package org.hhchat.leetcode.string;

import java.util.ArrayList;
import java.util.List;

/**
 * Created this one by HMH on 2017/11/26.
 */
public class code22_medium {

    static class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> list = new ArrayList<>();
            if(n == 0){
                return list;
            }
            int left = n;
            int right = n;
            StringBuilder sb = new StringBuilder();
            back(list, n, n, sb);
            return list;

        }
        public void back(List<String> list, int left, int right, StringBuilder sb){
            if (right == 0) {
                list.add(sb.toString());
                System.out.println(sb.toString());
                return ;
            }
            if(left < right){
                sb.append(")");
                back(list, left, right - 1, sb);
                sb.deleteCharAt(sb.length() - 1);
            }
            if (left > 0) {
                sb.append("(");
                back(list, left - 1, right, sb);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }

    public static void main(String[] args){
        System.out.println(new Solution().generateParenthesis(3));

    }


}
